package com.example.demo.leetcode.top100;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname Trie
 * @description
 * @date 2023/06/19 21:54
 * <p>
 * ******************************************************
 */
public class Trie {

    /**
     * 于都是小写字母，所以对于每个节点，均有 26 个孩子节点，
     * 但是要记住：每个节点均有 26 个孩子节点
     * 还有一个点要明确：节点仅仅表示从根节点到本节点的路径构成的字符串是否有效而已
     */
    class TrieNode {
        // 是否是结束节点
        boolean val;
        TrieNode[] children = new TrieNode[26];
    }

    private TrieNode root;


    public Trie() {
        this.root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (p.children[i] == null) {
                p.children[i] = new TrieNode();
            }
            p = p.children[i];
        }
        p.val = true;
    }

    public boolean search(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (p.children[i] == null) {
                return false;
            }
            p = p.children[i];
        }
        return p.val;
    }

    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for (char c : prefix.toCharArray()) {
            int i = c - 'a';
            if (p.children[i] == null) {
                return false;
            }
            p = p.children[i];
        }
        return true;
    }
}
